#include <vector>
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = nums.size() - 1; i > 2;)
        {
            long long three_sum = (long long)target - nums[i];
            if (target > 0 && three_sum > target)
                break;
            for (int j = i - 1; j > 1;)
            {
                long long two_sum = (long long)three_sum - nums[j];
                int left = 0, right = j - 1;
                while (left < right)
                {
                    if ((long long)nums[left] + nums[right] > two_sum)
                        --right;
                    else if ((long long)nums[left] + nums[right] < two_sum)
                        ++left;
                    else
                    {
                        // 满足条件，放入答案数组
                        ans.push_back({nums[left], nums[right], nums[j], nums[i]});
                        // 去重操作
                        ++left;
                        --right;
                        while (left < right && nums[left] == nums[left - 1])
                            ++left;
                        while (left < right && nums[right] == nums[right + 1])
                            --right;
                    }
                }
                // 外部也需要去重
                --j;
                while (j > 1 && nums[j] == nums[j + 1])
                    --j;
            }
            --i;
            // 这个也需要去重
            while (i > 2 && nums[i] == nums[i + 1])
                --i;
        }
        return ans;
    }
};